#include <stdio.h>

int print_arry(int *a, int len);
int swap(int *a, int *b);
int insert_sort(int *a, int len)
{
	int i,j,tmp;
	for(i=1;i<len;i++)
	{
		printf("*");
		print_arry(a,9);
		tmp = *(a+i);
		for(j=i-1;j>=0&&tmp<*(a+j);j--)
		{
			*(a+j+1) = *(a+j);
		}
		*(a+j+1) = tmp;
	}
	return 0;
}

int shell_sort(int *a, int len)
{
	int h,i,j,tmp;
	print_arry(a,9);
	for(h=len/2;h>0;h=h/2)
	{
	//	printf("h=%d\n",h);
		for(i=h;i<len;i++)
		{
			//printf("i=%d\n",i);
			//printf("*");
			
			tmp = *(a+i);
			for(j=i-h;(j>=0&&tmp<*(a+j)); j-=h)
			{
			//	printf("***j=%d\n",j);
				*(a+j+h)=*(a+j);
				print_arry(a,9);
			} 
			*(a+j+h)=tmp;
			print_arry(a,9);
		}
		print_arry(a,9);
	}
	return 0;
}

int bubble_sort(int *a, int len)
{
	printf("this is bubble_sort!\n");
	int i,j,exchange;
	for(i=0;i<len-1;i++)
	{
	//	printf("i=%d\n",i);
		exchange = 0;
		for(j=len-1;j>i;j--)
		{
			if(*(a+j-1)>*(a+j))
			{
		//		printf("**\n");
		//		tmp = *(a+j-1);
		//		*(a+j-1)=*(a+j);
		//		*(a+j)=tmp;
				*(a+j)^=*(a+j-1);
				*(a+j-1)^=*(a+j);
				*(a+j)^=*(a+j-1);
				exchange = 1;
				print_arry(a,9);
			}
		}
		if(!exchange)
		{
			return 0;
		}
	}
	return 0;
}

int print_arry(int *a, int len)
{
	int i;
	for(i=0;i<len;i++)
	{
		printf(" %d",*(a+i)); 
	}
	printf("\n");
	return 0;
}


int quick_sort(int *a, int low, int high)
{
	int i,j,pivot;
	if(low < high)
	{

		pivot = *(a+low);
		i = low;
		j = high;
		while(i<j)
		{
			while((i<j) && *(a+j)>pivot)
			{
				j--;
			}
			if(i<j)
			{
				*(a + i++) = *(a+j);
			}
			while(i<j && *(a+i)<= pivot)
			{
				i++;
			}
			if(i<j)
			{
				*(a + j--) = *(a+i);
			}
			*(a+i) = pivot;
		}
		quick_sort(a,low,i-1);
		quick_sort(a,i+1,high);
	}
	return 0;
}

int select_sort(int *a, int len)
{
	int i,j,x,l;
	for(i=0;i<len;i++)
	{
		x = a[i];
		l = i;
		for(j=i;j<len;j++)
		{
			if(a[j] < x)
			{
				x = a[j];
				l = j;
			}
		}
		a[l] = a[i];
		a[i] = x;
	}
	return 0;
}

int tree_left(int index)
{
	return ((index<<1)+1);
}

int tree_right(int index)
{
	return ((index<<1)+2);
}

int swap(int *a, int *b)
{
	*a ^= *b;
	*b ^= *a;
	*a ^= *b;
	return 0;
}

int max_heapify(int *array, int index, int heapsize)
{
	int largest = 0;
	int left = tree_left(index);
	int right = tree_right(index);

	if((left<=heapsize)&&(array[left]>array[index]))
	{
		largest = left;
	}
	else
	{
		largest = index;
	}
	if((right<=heapsize)&&(array[right]>array[largest]))
	{
		largest = right;
	}
	if(largest != index)
	{
		swap(&array[index],&array[largest]);
		max_heapify(array,largest,heapsize);
	}
	return 0;
}

int build_max_heap(int *array, int length)
{
	int i;
	for(i=(length-1);i>=1;i--)
	{
		max_heapify(array,i,length);
	}
	return 0;
}

int heap_sort(int *array, int len)
{
	int i;
	int heapsize=len-1;
	build_max_heap(array,len-1);
	for(i=(len-1);i>=1;i--)
	{
		swap(&array[0],&array[i]);
		heapsize--;
		max_heapify(array,0,heapsize);
	}
	return 0;
}
